#include "graph.hpp"

void graph_ergodic_test() {
    vector<string> vertexs = {"A", "B", "C", "D", "E", "F", "G", "H", "I"};
    clx_datastructure::graph<string, int>* g = new clx_datastructure::graph<string, int>(vertexs);
    g->addEdge("A", "B", 1);
    g->addEdge("A", "C", 1);
    g->addEdge("A", "D", 1);
    g->addEdge("B", "C", 1);
    g->addEdge("B", "E", 1);
    g->addEdge("C", "F", 1);
    g->addEdge("D", "F", 2);
    g->addEdge("E", "G", 3);
    g->addEdge("F", "H", 4);
    g->addEdge("H", "I", 4);

    g->bfs("A");
    g->dfs("A");
}

void graph_min_create_tree_test() {
    vector<string> vertexs = {"A", "B", "C", "D", "E", "F", "G", "H", "I"};
    clx_datastructure::graph<string, int>* g = new clx_datastructure::graph<string, int>(vertexs);
    g->addEdge("A", "B", 4);
    g->addEdge("A", "H", 8);
    g->addEdge("B", "H", 11);
    g->addEdge("B", "C", 8);
    g->addEdge("C", "D", 7);
    g->addEdge("C", "I", 2);
    g->addEdge("C", "F", 4);
    g->addEdge("D", "E", 9);
    g->addEdge("D", "F", 14);
    g->addEdge("E", "F", 10);
    g->addEdge("F", "G", 2);
    g->addEdge("G", "I", 6);
    g->addEdge("G", "H", 1);
    g->addEdge("H", "I", 7);

    clx_datastructure::graph<string, int>* min_g1 = new clx_datastructure::graph<string, int>(vertexs);
    clx_datastructure::graph<string, int>* min_g2 = new clx_datastructure::graph<string, int>(vertexs);
    int min_tree_weight = g->min_create_tree_kruskal(*min_g1);
    cout << min_tree_weight << endl;
    min_tree_weight = g->min_create_tree_prim(*min_g2);
    cout << min_tree_weight << endl;
}

void graph_dijstra_test() {
    vector<string> vertexs = {"s", "t", "x", "y", "z"};
    clx_datastructure::graph<string, int, INT_MIN, true>* g = new clx_datastructure::graph<string, int, INT_MIN, true>(vertexs);
    g->addEdge("s", "t", 10);
    g->addEdge("s", "y", 5);
    g->addEdge("t", "y", 2);
    g->addEdge("t", "x", 1);
    g->addEdge("y", "t", 3);
    g->addEdge("y", "z", 2);
    g->addEdge("y", "x", 13);
    g->addEdge("x", "z", 4);
    g->addEdge("z", "x", 6);
    g->addEdge("z", "s", 7);
  
    int min_path_weight = g->Dijkstra("s", "z");
    cout << min_path_weight <<endl;
}

void bellman_ford_test() {
    vector<string> vertexs = {"s", "t", "x", "y", "z"};
    clx_datastructure::graph<string, int, INT_MIN, true>* g = new clx_datastructure::graph<string, int, INT_MIN, true>(vertexs);
    g->addEdge("s", "t", 10);
    g->addEdge("s", "y", 5);
    g->addEdge("t", "y", 2);
    g->addEdge("t", "x", 1);
    g->addEdge("y", "t", 3);
    g->addEdge("y", "z", 2);
    g->addEdge("y", "x", 13);
    g->addEdge("x", "z", 4);
    g->addEdge("z", "x", 6);
    g->addEdge("z", "s", 7);
  
    int min_path_weight = g->Bellman_Ford("s", "z");
    cout << min_path_weight <<endl;
}

void FloydWarshall_test() {
    vector<string> vertexs = {"s", "t", "x", "y", "z"};
    clx_datastructure::graph<string, int, INT_MIN, true>* g = new clx_datastructure::graph<string, int, INT_MIN, true>(vertexs);
    g->addEdge("s", "t", 10);
    g->addEdge("s", "y", 5);
    g->addEdge("t", "y", 2);
    g->addEdge("t", "x", 1);
    g->addEdge("y", "t", 3);
    g->addEdge("y", "z", 2);
    g->addEdge("y", "x", 13);
    g->addEdge("x", "z", 4);
    g->addEdge("z", "x", 6);
    g->addEdge("z", "s", 7);

    int min_path_weight1 = g->Bellman_Ford("s", "z");
    vector<vector<int>> vvDest;
    vector<vector<int>> vvParent;

    g->FloydWarshall(vvDest, vvParent);
    cout << min_path_weight1 <<endl;
    int i = g->getVertexIndex("s"), j = g->getVertexIndex("z");
    cout << "z" << "<-";
    string tmp;
    while ((tmp = vertexs[vvParent[i][j]]) != "s") {
        cout << vertexs[vvParent[i][j]] << "<-";
        j = g->getVertexIndex(tmp);
    }
    cout << "s" << endl;
    
}



int main() {
    // graph_ergodic_test();
    // graph_min_create_tree_test();
    // graph_dijstra_test();
    // bellman_ford_test();
    FloydWarshall_test();
    return 0;
}





